# -*- coding: utf-8 -*-
def produce_insertionSort_results(inputs):
    tmp=[]
    res = []
    for i in range(len(inputs)):
        tmp.append(inputs[i])
        tmp.sort()
        print ' '.join(map(str,tmp + inputs[i+1:]))
        res.append(tmp + inputs[i+1:])
    return res
        
def produce_mergeSort_results(inputs):
    i=1
    res = []
    while i<len(inputs):
        i*=2
        t=[]
        for j in range(0,len(inputs),i):
            tmp=inputs[j:j+i]
            tmp.sort()
            t+=tmp
        print ' '.join(map(str,t))
        res.append(t)
        inputs=t
    return res

N=int(raw_input())
inputs=map(int,raw_input().split(' '))
tempo_res = map(int,raw_input().split(' '))

insertionsort_res = produce_insertionSort_results(inputs)
insertionsort_res.reverse()

if tempo_res in insertionsort_res:
    print 'Insertion Sort'
    try:
        print ' '.join(map(str,insertionsort_res[insertionsort_res.index(tempo_res)-1]))
    except:
        print ' '.join(map(str,insertionsort_res[0]))

mergesort_res = produce_mergeSort_results(inputs)
mergesort_res.reverse()

if tempo_res in mergesort_res:
    print 'Merge Sort'
    try:
        print ' '.join(map(str, mergesort_res[mergesort_res.index(tempo_res)-1]))
    except:
        print ' '.join(map(str, mergesort_res[0]))
